1. Field of the Invention
The present invention relates to a programming method for concurrent programs and a supporting apparatus for parallelization.
2. Description of the Related Art
Along with the recent progress in semiconductor integrated circuit technology, complex processors or large-capacity memories with a small size can be realized at a low cost, resulting in actual use of concurrent processing systems or distributed processing systems consisting of a large number of processors. Such hardware requires a dedicated program, i.e., a concurrent program or a distributed processing program (to be referred to as a "concurrent program" hereinafter). Therefore, efficient development of a concurrent program is an important factor as in examination of an excellent algorithm.
In program development, a step of finding and correcting a bug in a program (i.e., debug) largely influences the efficiency of program development. In development of a concurrent program, however, a problem inherent to a concurrent program, which is unfamiliar in development of a sequential program, must be taken into consideration. Such a problem inherent to a concurrent program is that processes constituting a concurrent program may exhibit various behaviors depending on timings of interaction among processes, so the entire concurrent program does not properly operate. This problem based on the nature of the concurrent program is generally called "nondeterminism".
Consider a concurrent program shown in FIGS. 1A and 1B.
Referring to FIG. 1A, a process P1 performs initialization (init) of a shared memory M, a process P2 performs read access (read) to the shared memory M, and a process P3 performs write access (write) to the shared memory M. When these processes are operated in in concurrent processing system which executes these processes by different processors, a total of six (FIG. 1B) combinations of operations are available. Normally, the system starts processing with initialization. Assume that a correct result is obtained when the program is operated in an order of processes P1 (init).fwdarw.P2 (read).fwdarw.P3 (write) or P1 (nit).fwdarw.P3 (write).fwdarw.P2 (read). In this case, as for the four remaining combinations (e.g., P2 (read).fwdarw.P3 (write).fwdarw.P1 (init)), since initialization is not performed first, a correct result cannot be obtained.
Whenever the concurrent program is operated, the above nondeterminism associated with the behaviors of processes change the result depending on the system status at that point of time. Therefore, unless the problem of nondeterminism is solved, the normal operation of the concurrent program cannot always be guaranteed although the concurrent program normally operates in a test mode.
In addition, it is difficult to detect a bug associated with nondeterminism as compared to a bug in a sequential program. In a sequential program, an operation can be confirmed by executing all paths in the program during a testing and debugging operation. To the contrary, in a concurrent program, paths must be executed in consideration of all matched paths (i.e., not only all paths in each process but also behaviors among processes). When the number of processes is small, as in the above example, all behaviors among the processes can be relatively easily listed. In actual program development, however, the number of processes becomes large to result in a large number of combinations thereof. For this reason, it is impossible to cover all behaviors.
As described above, debugging in concurrent program development is much more difficult than that in sequential program development. Especially, a program itself recently becomes very large to make debugging more difficult.